package algorithms.leaning.class17;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 打印一个字符串的全部排列，要求不要出现重复的排列
 *
 * @author guichang
 * @date 2021/6/16
 */

@SuppressWarnings("all")
public class Code5_递归_字符串全排列_去重 {

    public static void main(String[] args) {
        String str = "&cc";
        MyUtil.print(fullArray(str));
    }

    public static List<String> fullArray(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        List<String> list = new ArrayList<>();
        process(str.toCharArray(), 0, list);
        return list;
    }

    private static void process(char[] cs, int index, List<String> list) {
        if (index == cs.length) {
            list.add(new String(cs));
            return;
        }
        // 记录字符是否出现，注意：仅对普通英文字符起作用，中文字符长度超过256
        boolean[] visited = new boolean[256];
        // 每个位置都有可能为头
        for (int i = index; i < cs.length; i++) {
            if (!visited[cs[i]]) {
                visited[cs[i]] = true;
                swap(cs, index, i);
                process(cs, index + 1, list);
                swap(cs, index, i); // 恢复成进循环的样子，不然取到的下一个不是期望的样子
            }
        }
    }

    private static void swap(char[] cs, int i, int j) {
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }

}